An erasure can be characterized by a tuple of (n, k) parameters. The code word contains a total number of n symbols/columns, among which any k symbols/columns can be used to recover the other n-k symbols/columns in case they are lost. Erasure codes such as replication, RAID-5, and Reed-Solomon codes have long been used in storage systems for tolerating disk/node failures. To enable data recovery upon disk failures, Reed-Solomon codes need to store the lowest amount of redundant data, in which exactly m-disk worth of redundant data is preserved to tolerate arbitrary m disk failures. Codes with this property are called maximum-distance-separable (MDS) codes. On the other hand, replication requires much higher amount of redundant data, as large as or multiple times larger than the original data. However, replication has a much shorter recovery equation, meaning that it has higher recovery efficiency upon disk failures.
Flat XOR-Codes are the kind of codes between replication and MDS codes. Flat XOR-Codes are built solely on XOR operations. They have one-dimensional code structures, and each parity symbol is the XOR sum of a subset of the data symbols. Flat XOR-Codes are not MDS, so they are not as space-efficient as MDS codes. However, Flat XOR-Codes have much shorter recovery equations and their recovery efficiency is much higher than MDS codes. When compared with replication, Flat XOR-Codes are much more space-efficient, although their recovery efficiency is not as good. As a consequence, Flat XOR-Codes can provide elastic trade-offs between storage efficiency and recovery efficiency, thus giving more flexibility for storage systems in the choice of design parameters.
As the other kinds of non-MDS codes, there are Pyramid codes, WEAVER codes, and HOVER codes which sacrifice some storage efficiency for improving recovery efficiency. Pyramid codes are built on multiple levels of MDS codes, and the recovery is done in a level-by-level way like claiming up a pyramid. WEAVER and HOVER codes are non-systematic parity-array XOR-Codes, in which all or parts of the data columns contain parity symbols. However, these Erasure Codes are insufficient in storage efficiency and reconstruction performance.
With regard to Flat XOR-Codes, there are very few methods to construct Flat XOR-Codes, and the number of Flat XOR-Codes is very limited. Furthermore, the existing Flat XOR-Codes can only tolerate up to 3 failures.
Thus, what is needed is a more robust erasure code for data storage systems which optimizes a balance between storage efficiency and recovery efficiency. Furthermore, other desirable features and characteristics will become apparent from the subsequent detailed description and the appended claims, taken in conjunction with the accompanying drawings and this background of the disclosure.